POV : tu es un jardinier
Un arbre lexicographique (ou “trie”) est une structure utilisée pour représenter des ensembles dont les éléments admettent une décomposition séquentielle en “caractères” possédant de plus un ordre (par exemple, les entiers admettent une décomposition en suite de chiffres, les chaînes de caractères en suite de caractères, etc).
Un arbre lexicograhique contient :
De plus, les branches sont triées de gauche à droite. Pour chaque noeud, il doit être indiqué si la suite lue depuis la racine constitue la décomposition d’un élément ou seulement un préfixe strict d’une telle décomposition.
Il vous est demandé de ranger les “caractères” dans les branches. Un exemple d’arbre lexicographique stockant le long des branches les mots du mini-dictionnaire suivant : bas, bât, de, la, lai, laid, lait, lard, le, les, long est présenté sur la figure suivante :

Dans un premier temps, nous nous intéresserons juste à la structure arborescnete n-aire.
Exercice 1 (Définition des types) : Définir le type 'a arbre représentant la structure arborescente : arbre n-aire avec les booléens dans les noeuds et des 'a dans les branches. Vous pouvez également définir un second type représentant les branches.
type 'a arbre = Noeud of bool * ('a * 'a arbre) list
(* Solution du cours : *)
type 'a branche = 'a * 'a arbre
and 'a arbre = Noeud of bool * 'a branche list
(* Définition de l'arbre exemple *)
let bb = (b, Noeud(false, [...])
let bd = (d, Noeud(false, [...])
let bl = (b, Noeud(false, [...])
let b1 = [bb;bd;bl]
let arbre_sujet = Noeud(false,b1)
Exercice 2 (Test d’appartenance) : Ecrire la fonction appartient qui teste si un élément appartient bien à un ensemble représenté par un arbre lexicographique.
(* Contrat
recherche : 'a -> ('a * 'b) list -> 'b option - Retourne une branche
commançant par un caractère donné s'il en exite une.
Paramètres :
- c : 'a - caractère
- lb : ('a * 'b) list - liste de branches
Résultat : 'b option - Branche qui commence par c si ça existe
*)
let rec recherche c lb =
match lb with
| [] -> None
| (carock,abr)::q ->
if carock > c then
None
else
if carock = c then
Some abr
else
recherche c q
(* Contrat
appartient : 'a list -> 'a arbre -> bool - Retourne si un élément
est dans un ensemble représenté par un arbre lexicographique
Paramètres :
- m : 'a list - élément à rechercher
- abr : 'a arbre - arbre lexicographique
Résultat : bool - Vrai si x est dans abr, faux sinon
*)
let rec appartient m (Noeud(b,l)) =
match m with
| [] -> b
| t::q ->
match recherche t l with
| None -> false
| Some(x) -> appartient q x
Exercice 3 (Ajout) : Ecrire la fonction ajout qui ajoute un élément à un ensemble représenté par un arbre lexicographique.
(* Contrat
maj : 'a -> 'b -> ('a * 'b) list -> ('a * 'b) list -
Met à jour une branche avec un caractère donné dans la liste de branches
avec la nouvelle branche donnée.
Paramètres :
- c : 'a - caractère
- b : 'b - la branche
- lb : ('a * 'b) list - la liste des branches
Résultat : ('a * 'b) list - la liste des branches avec la branche mise à jour
*)
let rec maj c b lb =
match lb with
| [] -> [c,b]
| (tc,ta)::q ->
if c < tc then
(c,b)::lb
else
if c = tc then
(c,b)::q
else
(tc,ta)::(maj c b q)
(* Contrat
ajout : 'a list -> 'a arbre -> 'a arbre -
Ajoute un élément dans un arbre lexicographique
Paramètres :
- m : 'a list - élément à ajouter à l'arbre
- abr : 'a arbre - arbre lexicographique
Résultat : 'a arbre - arbre où m a été ajouté à abr
*)
let rec ajout m (Noeud(b,lb)) =
match m with
| [] -> Noeud(true,lb)
| c::q ->
let arbrec =
match recherche c lb with
| None -> Noeud(false, [])
| Some branche -> branche
in Noeud(b, maj c (ajout q arbrec) lb)
En plus de la structure arborescente, un arbre lexicographique contient une fonction de décomposition et une fonction de recomposition.
Par exemple, dans le cas d’un dictionnaire de mot, la fonction de décomposition sera de type string -> char list et la fonction de recomposition de type char list -> string, permettant par exemple de passer de "laid" à ['l';'a';'i';'d'].
Exercice 4 : Définir le type ('a,'b) trie permettant de représenter des arbres lexicographiques (arbres + fonction de décomposition + fonction de recomposition).
type ('a,'b) trie = Trie of 'b arbre * ('a -> 'b list) * ('b list -> 'a)
(*
'a -> 'b list : fonction de décomposition
'b list -> 'a : fonction de recomposition
*)
Exercice 5 (Test d’appartenance) : Ecrire la fonction appartient_trie qui teste si un élément appartient bien à un ensemble représenté par un arbre lexicographique.
(* Contrat
appartient_trie : 'a -> ('a,'b) trie -> bool -
Teste si un élément appartient à un ensemble représenté
par un arbre lexicographique
Paramètres :
- mot : 'a - élément cherché
- Trie(a,fd,fr) - arbre lexicographique
Résultat : bool - Vrai si l'élément est dans l'arbre, faux sinon
*)
let appartient_trie mot Trie(a, fd, fr) =
let lmot = fd mot in appartient (fd lmot) a
Exercice 6 (Ajout) : Ecrire la fonction ajout_trie qui ajoute un élément à un ensemble repésenté par un arbre lexicographique.
(* Contrat
ajout_trie : 'a -> ('a,'b) trie -> ('a,'b) trie -
Ajoute un élément à un ensemble représenté
par un arbre lexicographique
Paramètres :
- mot : 'a - élément à ajouter
- Trie(a,fd,fr) : ('a,'b) trie - arbre lexicographique
Résultat : ('a,'b) trie - Arbre de départ où on a ajouté mot
*)
let ajout_trie mot Trie(a, fd, fr) =
let lmot = fd mot in Trie(ajout (fd lmot) a, fd, fr)